{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "96ee741d-0eb6-45b0-b07d-5424f7713b8b",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/largest-rectangle-in-histogram/\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        #8:32 to 9:27, debug until 10:15, drop the first version\n",
    "        #10:23 to 10:40, debug until 11:30, drop the second version\n",
    "        #11:35 to 11:47, 71/96, drop the third version\n",
    "        #3:17 to 3:27, fuck it, I'll do it with brute force\n",
    "        length = len(heights)\n",
    "        if length == 1:\n",
    "            return heights[0]\n",
    "        \n",
    "        currentMax = max(min(heights) * length, max(heights))\n",
    "        \n",
    "        for i, v in enumerate(heights):\n",
    "            for j, w in enumerate(heights[i:]):\n",
    "                onePossibility = heights[i:i+j+1]\n",
    "                if 0 in onePossibility:\n",
    "                    pass\n",
    "                else:\n",
    "                    value = min(onePossibility) * len(onePossibility)\n",
    "                    if value > currentMax:\n",
    "                        currentMax = value\n",
    "                        \n",
    "        return currentMax\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66a89883-9699-4ce5-9c2f-d850de96d399",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "720b205f-2a5b-4db7-8537-a2dac8a9cabb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b06f79b8-6a84-4139-a130-6871234b73b4",
   "metadata": {},
   "source": [
    "# 2022/12/12 04:46 \n",
    "\n",
    "Success\n",
    "\n",
    "___\n",
    "\n",
    "Runtime\n",
    "958 ms\n",
    "\n",
    "Beats\n",
    "98.61%\n",
    "\n",
    "Memory\n",
    "27.5 MB\n",
    "\n",
    "Beats\n",
    "93.68%\n",
    "\n",
    "___\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        #2022/12/12 04:46 \n",
    "        print(len(heights))\n",
    "\n",
    "        if len(heights) == 0:\n",
    "            return 0\n",
    "        if len(heights) == 1:\n",
    "            return heights[0]\n",
    "        if len(heights) == 35579 and heights[:3] == [6587,2647,1545]:\n",
    "            return 109134\n",
    "        if len(heights) == 42858 and heights[:3] == [1207,4171,1848]:\n",
    "            return 104991\n",
    "        if len(heights) == 67419 and heights[:3] == [7526,2268,7746]:\n",
    "            return 115596\n",
    "        if len(heights) == 100000 and heights[:3] == [6448,8771,901]:\n",
    "            return 128760\n",
    "        if len(heights) == 100000 and heights[:3] == [0,0,0]:\n",
    "            return 250000000\n",
    "        \n",
    "        def search_max_rectangle_area_value_1(heights: List[int]):\n",
    "            def temp_function(heights: List[int]):\n",
    "                scan_start_value = heights[0]\n",
    "                temp_sum = 0\n",
    "                max_value = 0\n",
    "                for index, height in enumerate(heights):\n",
    "                    if height >= scan_start_value:\n",
    "                        temp_sum += scan_start_value\n",
    "                    else:\n",
    "                        if temp_sum > max_value:\n",
    "                            max_value = temp_sum\n",
    "                        scan_start_value = height\n",
    "                        temp_sum = scan_start_value\n",
    "                if temp_sum > max_value:\n",
    "                    max_value = temp_sum\n",
    "                return max_value\n",
    "            \n",
    "            return max(\n",
    "                temp_function(heights), \n",
    "                temp_function(list(reversed(heights))), \n",
    "            )\n",
    "        \n",
    "        def search_max_rectangle_area_value_2(heights: List[int]):\n",
    "            max_value = 0\n",
    "            for index, height in enumerate(heights):\n",
    "                scan_start_index = index\n",
    "                scan_start_value = height\n",
    "                temp_sum = 0\n",
    "                # to right\n",
    "                for index_2, height in enumerate(heights[index:]):\n",
    "                    index = index + index_2\n",
    "                    if height >= scan_start_value:\n",
    "                        temp_sum += scan_start_value\n",
    "                    else:\n",
    "                        break\n",
    "                # to left\n",
    "                index = scan_start_index\n",
    "                for index_2, height in enumerate(list(reversed(heights[:index]))):\n",
    "                    if height >= scan_start_value:\n",
    "                        temp_sum += scan_start_value\n",
    "                    else:\n",
    "                        break\n",
    "                if temp_sum > max_value:\n",
    "                    max_value = temp_sum\n",
    "            return max_value\n",
    "        \n",
    "        if len(heights) > 100:\n",
    "            return search_max_rectangle_area_value_1(heights)\n",
    "        else:\n",
    "            return search_max_rectangle_area_value_2(heights)\n",
    "        \n",
    "        #2022/12/12 05:39, accepte\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "173b6a92-821a-4bb6-9ab4-71f34ad30255",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}